/*
 * @lc app=leetcode.cn id=307 lang=cpp
 *
 * [307] 区域和检索 - 数组可修改
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class NumArray
{
public:
    const long long NUM = 1000;
    const long long nums_size;
    vector<int> &nums;
    vector<long long> dp;
    NumArray(vector<int> &nums) : nums(nums), nums_size(nums.size())
    {
        // NUM = max(NUM, (long long)(sqrt((long long)nums_size)));

        for (long long i = 0; i < nums_size / NUM * NUM; i += NUM)
        {
            int sum = accumulate(nums.begin() + i, nums.begin() + i + NUM, 0);
            dp.push_back(sum);
        }
    }

    inline long long down(long long index)
    {
        return index - index % NUM;
    }
    inline long long up2(long long index)
    {
        return min(down(index) + NUM - 1, (nums_size - 1));
    }

    void update(long long index, long long val)
    {
        if (nums_size >= NUM)
        {
            dp[index / NUM] += val - nums[index];
        }
        nums[index] = val;
    }

    int sumRange(long long left, long long right)
    {
        if (left > right)
            return 0;
        if (left == right)
            return nums[left];

        long long sum = 0;
        const int down_left = down(left);
        const int down_right = down(right);
        int dp_left = left / NUM;
        const int dp_right = right / NUM;

        if (down_left == down_right)
        {
            sum = accumulate(nums.begin() + left, nums.begin() + right + 1, 0);
        }
        else
        {
            //[down_left,left-1]需要被减去
            sum -= sumRange(down_left, left - 1);

            while (dp_left < dp_right)
            {
                sum += dp[dp_left];
                dp_left++;
            }

            //[down_right, right]还没有加上
            sum += sumRange(down_right, right);
        }
        return sum;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * long long param_2 = obj->sumRange(left,right);
 */

// int main()
// {
//     vector<int> nums = {1, 3, 5};
//     NumArray obj(nums);
//     obj.sumRange(0, 2);
//     obj.update(1, 2);
//     obj.sumRange(0, 2);
//     return 0;
// }

// @lc code=end
